- Title
- A note on shortest path problems with forbidden paths
- Creator
- Smith, Olivia J.; Savelsbergh, Martin W. P.
- Relation
- ARC
- Relation
- Networks Vol. 63, Issue 3, p. 239-242
- Publisher Link
- http://dx.doi.org/10.1002/net.21541
- Publisher
- Wiley-Blackwell Publishing Ltd
- Resource Type
- journal article
- Date
- 2014
- Description
- We consider the variant of the shortest path problem in which a given set of paths is forbidden to occur as a subpath in an optimal path. We establish that the most-efficient algorithm for its solution, a dynamic programming algorithm, has polynomial time complexity; it had previously been conjectured that the algorithm has pseudo-polynomial time complexity. Furthermore, we show that this algorithm can be extended, without increasing its time complexity, to handle non elementary forbidden paths.
- Subject
- shortest path; forbidden path; dynamic programming; algorithm
- Identifier
- http://hdl.handle.net/1959.13/1067849
- Identifier
- uon:18496
- Identifier
- ISSN:0028-3045
- Language
- eng
- Reviewed
- Hits: 782
- Visitors: 712
- Downloads: 0
Thumbnail | File | Description | Size | Format |
---|